package com.hsj.p01;

import java.util.Arrays;

/**
 * 二分查找  前提有序, 缩小范围
 * 设置两个指针， 指向数组两端 左端i 右端j ，当i在j左侧 或 i和j相交 就执行循环 查找逻辑， 当i 跑到 j 的右侧，就返回失败结果
 * 在循环内 取 i和j 的中间位置m, 将目标 和 中间元素比较，
 * 如果目标 比 中间元素 小 说明 目标在 数组左侧， 缩小范围到左半部分 也就是将 j = m-1;
 * 如果目标 比 中间元素 大 说明 目标在 数组右侧， 缩小范围到右半部分 也就是将 i = m+1;
 * 如果目标 和 中间元素 相等 说明 目标找到
 * <p>
 * 最坏情况 O(logN)
 * 最好情况 O(1)
 * <p>
 * 补充
 * 无符号 10010101  首位不代表符号
 * 有符号 10010101  首位代表正负
 * java 都是有符号的，所以为了避免因为符号导致表达不正确， 可以用过 右移的方式 = 除以2取整
 * 举例  10010101   >>> 1  01001010
 * 注意：
 * 1. 为什么循环条件是 i<=j  而不是i<j? 因为可能 i=j 的位置刚好就是找到的元素，如果少了= 就少比较了一次  ,
 * 比较的时候都是拿 a[m] i和j 中间的元素和 target 进行比较, i=j m和i,j 都指向同一个位置，所以比较在比较一次.
 */
public class BinarySearch {
    public static void main(String[] args) {
        int target =4;
        int[] arr = {2,5,8};
        int chaRuDian = Arrays.binarySearch(arr, target); //如果key存在于数组 返回的是下标， 如果不存在于数组，返回的是插入点 例如6不在数组arr里，返回插入点-2
        //为什么 不return -low  而是 return -(low+1)  ？ 为了区分 0 的这种情况
        int insertIndex= Math.abs(chaRuDian + 1);//将插入 变为索引诶值  并取绝对值
/**           [2,5,8] arr
         *    [2,0,0,0] newArr
         *    [2,4,0,0] newArr
         *    [2,4,5,8] newArr
         */
        int[] newArr = new int[arr.length+1];
        System.arraycopy(arr,0,newArr,0,insertIndex);  // [2,0,0,0] newArr
        newArr[insertIndex] = target;                   // [2,0,0,0] newArr
        System.arraycopy(arr,insertIndex,newArr,insertIndex+1,arr.length - insertIndex);//[2,4,5,8] newArr
    }

    public static int binarySearchBasic(int[] a, int target) {
        int i = 0, j = a.length - 1;
        while (i <= j) {
            int m = (i + j) / 2;  //取整,  如果 j是int最大值，加上i , 结果就成了 负数
            if (target < a[m]) {  //目标在中间值左边
                j = m - 1;
            }
            if (a[m] < target) {
                i = m + 1;
            } else {
                return m;
            }
        }
        return -1;
    }


    public static int binarySearchBasic1(int[] a, int target) {
        int i = 0;
        int j = a.length - 1;
        while (i <= j) {
            int m = (i + j) >>> 1;  // 优化 将 (i+j)/2 优化为  (i+j) >>> 1
            if (target < a[m]) {  //目标在中间值左边
                j = m - 1;
            }
            if (target > a[m]) {
                i = m + 1;
            } else {
                return m;
            }
        }
        return -1;
    }


    //优化   O(logN)
    public static int binarySearchBasic3(int[] a, int target) {

        int i = 0;
        int j = a.length;
        while (1 < j - i) {
            int m = (i + j) >>> 1;
            if (target < a[m]) {
                j = m;
            } else {
                i = m;
            }
        }
        if(a[i] == target){
            return i;
        }else{
            return -1;
        }
    }


/**     LeftMost
 *  由于 二分查找在 没有重复元素的情况下 能以O(logN)时间复杂度 找到，
 *  如何找到 重复元素中 最左边的元素下标
 *
 *  使用场景  求排名   排名= leftMost(元素)+1
 *          求前任   前任= leftMost(元素) -1
 *          求后任   后任- leftMost(元素) +1
 *          最近邻居  从前后任找 距离最小的
 *          1 2 4 4 4 7 7
 *          <4    0 到 leftMost(4)
 *          <=4   0 到 rightMost(4)
 *          >4    rightMost(4)+1      到 无穷大
 *          >=4   leftMost(4)         到 无穷大
 *          4<=x<=7 leftMost(4) .. rightMost(7)
 *          4<x<7  rightMost(4)+1 ... leftMost(7)-1
 */
public static int binarySearchLeftmost4(int[]a , int target){
    int i = 0 ;
    int j = a.length -1;
    int candidate = -1;
    while(i <= j) {
        int m = (i+j)>>>1;
        if(target<a[m]){
            j = m-1;
        } else if(target>a[m]){
            i = m+1;
        }else {
            candidate = m;
            j = m - 1;
        }
    }
    return candidate;
}
//----------------优化
    public static int binarySearchLeftmost4yh(int[]a , int target){
        int i = 0 ;
        int j = a.length -1;
        while(i <= j) {
            int m = (i+j)>>>1;
            if(target <= a[m]){
                j = m-1;
            } else if(target>a[m]){
                i = m+1;
            }
        }
        return i;
    }


/**         RightMost
 *     重复元素中  最左边的元素下标
 */
public static int binarySearchLeftmost5(int[]a , int target){
    int i = 0 ;
    int j = a.length -1;
    while(i <= j) {
        int m = (i+j)>>>1;
        if(target<a[m]){
            j = m-1;
        }else {
            i = m + 1;
        }
    }
    return i-1;
}




}
